package com.ds.bintree.LeetCode;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: 后序遍历递归方法
 * @date 2022/9/12 23:49
 */
public class Num236_LowestCommonAncestor2 {
    TreeNode anc;
    /**
     * 该子树是否包含指定结点p或者q
     * @param root
     * @param p
     * @param q
     * @return
     */
    public boolean isContains(TreeNode root,TreeNode p,TreeNode q){
        if (root==null){
            return false;
        }
        boolean left=isContains(root.left,p,q);
        boolean right=isContains(root.right,p,q);
//      如果左右子树都包含q和p，就是最近公共祖先
//      如果左右子树只包含一个p或者q并且当前结点就是p或者q,则当前结点就是最近公共祖先
        if (left&&right){
            anc=root;
            return true;
        }
        if (left||right){
            if (root.val== q.val || root.val == p.val){
                anc=root;
            }
            return true;
        }
        return root.val == q.val || root.val == p.val;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        isContains(root,p,q);
        return anc;
    }
}
